Masala #0969

Xotira 64 MB Vaqt 1250 ms Qiyinchiligi 59 %
14

  

Sonlar o`qidagi girlyanda #1

Masalaning #1 va #2 versiyalari tubdan farq qiladi. Ularni alohida masalalar sifatida hisoblash to`g`riroqdir.

Yangi yilda arafasida, yangi yil ruhini bag`ishlovchi har xil bezak buyumlari mavjud. Asilbekka eng yoqgani - girlyandadir. Uni istalgan joyga ossa bo`ladi, devorga, mebelga, archaga... Asilbek esa girlyandani sonlar o`qiga osilganini ham ko`rgan!

Asilbek o`zining sevimli sonlar o`qining musbat tomoniga qarasa, u to`liq girlyanda bilan bezatilgan ekan. Bunda \(a\) va \(b(a \neq b)\) sonlar girlyanda bilan bog`langan, agarda \(a|b\) yoki \(b|a\) (bir sonni ikkinchisini qoldiqsiz bo`ladi) sharti qanoatlantirsa.

Payqash qiyin emaski, 1 sonidan girlyandalar orqali boshqa barcha sonlarga borish mumkin. Girlyanda orqali faqat katta songa o`tish mumkin bo`lsa, 1 sonidan \(A\) sonigacha eng ko`pi bilan nechta o`tish yordamida yetib olsa bo`ladi?


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 2*10^5)\) testlar soni kiritiladi.

Keyingi  \(T\) ta qaorning har birida bittadan butun son - \(A(2 \leq A \leq 10^7)\) soni kiritiladi.


Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda bitta butun son, masala javobini chop eting.


Misollar
# input.txt output.txt
1
3
12
4
7
3
2
1
2
2
100
8
4
3
Izoh:

1-test:

1 dan 12 ga yetish uchun eng uzun yo`l: 1 -> 2 -> 6 -> 12

2-test:

1 dan 100 ga yetish uchun eng uzun yo`l: 1 -> 5 -> 25 -> 50 -> 100

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin